﻿// 3999. 最大公约数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4002/

给定两个正整数 a,m
，其中 a<m
。

请你计算，有多少个小于 m
 的非负整数 x
 满足：

gcd(a,m)=gcd(a+x,m)

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据占一行，包含两个整数 a,m
。

输出格式
每组数据输出一行结果，一个整数，表示满足条件的非负整数 x
 的个数。

数据范围
前三个测试点满足，1≤T≤10
。
所有测试点满足，1≤T≤50
，1≤a<m≤1010
。

输入样例：
3
4 9
5 10
42 9999999967
输出样例：
6
1
9999999966
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 